La tortue et le scarabée

Cette activité se propose d'explorer les déplacements sur une grille à l'aide de plusieurs codes écrits en Python. Dans toute l'activité, les déplacements sont réalisés sur des grilles rectangulaires et se réalisent uniquement suivant les côtés des carreaux qui composent chaque grille, en parcourant, à chaque pas, un côté d'un carreau.

Partie A : les déplacements de la tortue

Une tortue se trouve dans le coin en bas à gauche d'une une grille de dimensions \(2\times 3\). Elle se déplace pour atteindre le sommet opposé à celui où elle se trouve.
Les déplacements possibles de la tortue sont : vers le \(\texttt{haut}\), vers le \(\texttt{bas}\), vers la \(\texttt{gauche}\) ou vers la \(\texttt{droite}\).
Pour modéliser la situation, on considère que la tortue se trouve à l'origine d'un repère orthonormé. Ainsi, le point \(\texttt{depart}\) a pour coordonnées \((0~;0)\) et le point d'arrivée a pour coordonnées \((3~;2)\).
On s’intéresse aux chemins possibles pour partir du point \(\texttt{depart}\) et arriver au point nommé \(\texttt{cible}\) qui aura pour coordonnées \((3~;2)\).

1. Quel est le nombre de chemins possibles pour la tortue qui n'utilisent que les déplacements \(\texttt{haut}\) et \(\texttt{droite}\) ?
Le code ci-après simule tous les chemins possibles.

https://capytale2.ac-paris.fr/web/c/d39a-6864078

2. Exécuter le code afin de vérifier si la réponse donnée à la question 1. est correcte.
3. Toujours en utilisant uniquement les déplacements \(\texttt{haut}\) et \(\texttt{droite}\), quel est le nombre de chemins possibles lorsque la grille est un carré de côté \(4\) et que la tortue veut se déplacer du point de coordonnées \((0~;0)\)  au point de coordonnées \((4~;4)\) ?
Modifier le code afin de vérifier le nombre de chemins possibles dans cette deuxième situation.

Partie B : les chemins d'un scarabée 

Un scarabée se trouve dans le coin en bas à gauche d'une une grille de dimensions \(2\times 3\). Il se déplace pour atteindre le sommet opposé à celui où il se trouve. Pour modéliser la situation, on considère que le scarabée se trouve à l'origine d'un repère orthonormé. Ainsi, le point \(\texttt{depart}\) a pour coordonnées \((0~;0)\) et le point d'arrivée a pour coordonnées \((3~;2)\).

Le code, incomplet, ci-dessous a l'objectif de permettre à l'utilisateur de saisir \(4\) commandes : \(\texttt{haut}\;;\;\texttt{bas}\;;\;\texttt{gauche}\;;\;\texttt{droite}\) correspondant aux déplacements souhaités du scarabée.
Les variables \(\texttt{horiz}\;;\;\texttt{verti}\) correspondent, respectivement, à la coordonnée horizontale et à la coordonnée verticale de la position du scarabée sur la grille.
Autrement dit, le point de départ est repéré par les valeurs \(\texttt{horiz}=0\;;\;\texttt{verti}=0\) et le point d'arrivée par les valeurs \(\texttt{horiz}=3\;;\;\texttt{verti}=2\).
Le code s'arrête lorsque le scarabée atteint le point d'arrivée.

La documentation Python donne les indications suivantes : 
« input(prompt)
Si l'argument prompt est donné, il est écrit sur la sortie standard sans le retour à la ligne final. La fonction lit ensuite une ligne sur l'entrée standard et la convertit en chaîne (supprimant le retour à la ligne final) qu'elle renvoie. »

Ainsi la variable \(\texttt{deplacement}\) contiendra la chaîne de caractère entrée par l'utilisateur.

1. Compléter le code.
2. Modifier le code afin qu'il alerte lorsque le scarabée sort de la grille.
3. Compléter le code pour qu'il compte le nombre de déplacements réalisés pour aller du point de départ au point d'arrivée et qu'il affiche ce nombre.
4. Quel semble être le plus petit nombre de déplacements nécessaires pour aller du point de départ au point d'arrivée ?
5. Modifier la position d'arrivée et répéter la question 4.
6. Conjecturer le nombre minimal de déplacements nécessaires pour une grille de dimensions \(n\times m\) avec \(n,m\) deux entiers naturels.

Partie C : un chemin aléatoire

Dans cette partie, le choix du déplacement pour aller du point de départ au point d'arrivée est aléatoire. Dans ce cas, on parle de « marche aléatoire ».
Pour simplifier, on supposera d'une part que la grille est infinie, donc que les coordonnées peuvent être négatives, et, d'autre part, que, si le scarabée n'a pas atteint le point d'arrivée en moins de \(20\) mouvements, alors il ne l'atteindra pas dans un temps raisonnable.

Pour faciliter le travail on utilisera le code partiel donné dans la partie B et on le complétera grâce aux indications suivantes.

• Placer dans une liste \(\texttt{possibilites}\) les quatre déplacements possibles \(\texttt{haut ; bas ; gauche ; droite}\).
• Importer la bibliothèque \(\texttt{random}\).
• Créer une variable qui comptera le nombre de déplacements de chaque chemin.
  
• Créer une liste qui permettra de stocker les longueurs de chaque chemin qui mènera de \(\texttt{depart}\) à \(\texttt{cible}\) et seulement la longueur de ceux-là.
• Utiliser la méthode \(\texttt{randint}\) pour générer un nombre aléatoire compris entre \(0\) et \(3\), ce nombre correspondra à l'indice du déplacement à effectuer dans la liste \(\texttt{possibilites}\) : on aura donc \(\texttt{deplacement = possibilites[randint(0,3)]}\).
  
• Ajouter comme condition d'arrêt de la boucle \(\texttt{while}\) donnée dans le code incomplet un test qui permet d'arrêter les tirages aléatoires de déplacements si la longueur du chemin est strictement supérieure à \(20\).
  
• Répéter \(1\;000\) fois cette marche aléatoire.
• Calculer le nombre de chemins, parmi ces \(1\;000\), qui ont permis d'atteindre le point d'arrivée et afficher la fréquence de succès.
  
• Calculer et afficher la longueur moyenne des chemins aléatoires qui ont permis d’atteindre le point d'arrivée.  
  

Modifier la longueur maximum du chemin et exécuter le code : que constate-t-on ?
Si besoin, le code complet est proposé ci-après.